#include <stdio.h>
#include <stdlib.h>
#include <err.h>
#include <assert.h>
#include "network.h"

/**
 * @file   network.c
 * @Author Pellegrini Franco (frapell@gmail.com)
 * @date   Abril, 2011
 * @brief  Archivo con definicion de estructuras y funciones
 *
 */

/**
 * @brief Estructura Network
 * 
 * Estructura que representa un nodo
 */
struct sNodo{
    /** Label del Nodo */
    u32 label;
    /** Cantidad de nodos forward que tengo */
    u32 gradofwd;
    /** Capacidades de cada arista (Lados FWD) */
    u32* capacidades;
    /** Lista de indices de los nodos FWD */
    Nodo* nodosfw; 
};

/**
 * @brief Estructura Network
 * 
 * Estructura donde se almacenan todos los nodos cargados
 */
struct sNetwork{
    /** Lista de todos los nodos del grafo */
    Nodo* nodos;
    /** Cantidad de nodos del grafo */
    u32 cant_nodos; 
};


/**
 * @brief Estructura Path
 * 
 * Esta estructura se utiliza para generar el camino mas corto de 0 a 1
 */
struct sPath{
    /** Lista de nodos */
    Nodo* nodos;
    /** Indice en "nodos" que corresponde a quien agrego el nodo a la lista */
    u32* padre;
    /** La capacidad del lado */
    u32* capacidad;
    /** El bfs terminado */
    u32* bfs;
    /** Longitud del camino bfs */
    u32 largo_bfs;
    /** Cantidad de elementos en "nodos" */
    u32 size;
    /** Posicion donde me encuentro parado en el path */
    u32 position;
    /** Flujo maximo posible de enviar por el camino bfs */
    u32 flujo; 
};

/** @defgroup network Funciones de la estructura Network
 *  @{
 */
/*Inicio seccion "Network"*/

Network
crear_network(void){
    /**
    * @param void 
    *
    * @retval network Network creado
    * 
    * Esta funcion asigna la memoria inicial para una estructura de tipo
    * Network.
    * Anula la ejecucion si encuentra un error.
    * En caso de exito, devuelve el Network
    */

    Network network=NULL;

    network = (Network)calloc(1,sizeof(struct sNetwork));
    if (network == NULL){
        perror("calloc");
        assert(network!=NULL);
    }

    network->nodos = NULL;
    network->cant_nodos = 0;
    
    return network;
}


void
destruir_network(Network network){
    /**
    * @param network Network a destruir
    *
    * @retval void 
    * 
    * Destructor del tipo Network
    */

    u32 i = 0;
    
    for (i=0;i<network->cant_nodos;i++){
        destruir_nodo(network->nodos[i]);
        network->nodos[i] = NULL;
    }
    free(network->nodos);
    free(network);
    
    return;
}


void
agregar_nodo(Network network, Nodo nodo){
    /**
    * @param network Network al cual agregamos el nodo
    * @param nodo Nodo a agregar
    *
    * @retval void 
    * 
    * Funcion que agrega un nodo a la estructura del network.
    * Se anula la ejecucion si se encuentra un error.
    * En caso de exito, no se devuelve nada.
    */
    
    if (network->nodos == NULL){
        /*
         * Primer nodo a agregar, asignamos memoria
         */
        network->nodos = (Nodo*)calloc(1,sizeof(struct sNodo));
        if (network->nodos == NULL){
            perror("calloc");
            assert(network->nodos!=NULL);
        }
    }    
    else{
        /*
         * No es el primer nodo, asi que reallocamos
         */

        network->nodos = (Nodo*)realloc(\
                                network->nodos,\
                                sizeof(Nodo)*(network->cant_nodos + 2));
        if (network->nodos == NULL){
            perror("realloc");
            assert(network->nodos!=NULL);
        }
    }
    /*
     * En este momento, deberiamos tener el espacio de memoria apropiado
     * en la estructura, para meter el nodo
     */
    network->nodos[network->cant_nodos] = nodo;
    /*
     * Incrementamos la variable de cantidad de nodos
     */
    network->cant_nodos++;

    return;
}


Nodo
obtener_nodo(Network network, u32 label){
    /**
    * @param network Network en donde buscamos
    * @param label Nombre del nodo buscado
    *
    * @retval nodo Nodo en caso de encontrarse, NULL caso contrario
    * 
    * Funcion que obtiene un "Nodo" con "label" label.
    * NULL en caso de no encontrarlo
    */
    
    Nodo nodo = NULL;
    u32 i = 0;
    int found = 0;

    while (i<network->cant_nodos && !found){
        /*
         * Itero sobre todos los nodos del network
         */
        if (network->nodos[i]->label == label){
            /*
             * Si encontre el que buscaba, lo asigno a "nodo"
             */
            nodo = network->nodos[i];
            found = 1;
        }
        i++;
    }

    /*
     * Finalmente, lo devuelvo
     */
    return nodo;
}


void
agregar_lado(Network network, u32 padre, u32 hijo, u32 capacidad){
    /**
    * @param network Network al cual agregamos el lado
    * @param padre Nodo padre
    * @param hijo Nodo hijo
    * @param capacidad Capacidad del lado
    *
    * @retval void 
    * 
    * Esta funcion toma un nodo padre, su hijo y la capacidad del lado
    * y lo agrega a la estructura (solo si la capacidad del lado es > 0)
    */
    
    Nodo nodo_padre = NULL;
    Nodo nodo_hijo = NULL;

    if (capacidad > 0){
        nodo_padre = obtener_nodo(network, padre);
        if (nodo_padre == NULL){
            /*
            * El nodo padre no existe, lo creo de cero y lo agrego al network
            */
            nodo_padre = nodo_create(padre);
            agregar_nodo(network, nodo_padre);
        }
        nodo_hijo = obtener_nodo(network, hijo);
        if (nodo_hijo == NULL){
            /*
            * El nodo hijo no existe, lo creo de cero y lo agrego al network
            */
            nodo_hijo = nodo_create(hijo);
            agregar_nodo(network, nodo_hijo);
        }

        /*
        * En este momento, deberia tener ambos nodos, ahora solo falta
        * que los relacione
        */

        agregar_nodo_fwd(nodo_padre, nodo_hijo, capacidad);
    }

    return;
}

/** @} */ /*Final seccion "Network"*/


/** @defgroup nodo Funciones de la estructura Nodo
 *  @{
 */
/*Inicio seccion "Nodo"*/

Nodo
nodo_create(u32 label){
    /**
    * @param label Nombre del nodo
    * 
    * @retval nodo Nodo creado
    * 
    * Esta funcion asigna la memoria inicial para una estructura de tipo
    * Nodo.
    * Anula la ejecucion si encuentra un error.
    * En caso de exito, devuelve el Nodo
    */
    
    Nodo nodo;
    nodo = (Nodo)calloc(1,sizeof(struct sNodo));
    if (nodo == NULL){
        perror("calloc");
        assert(nodo!=NULL);
    }
    nodo->label = label;
    nodo->gradofwd = 0;
    nodo->capacidades = NULL;
    nodo->nodosfw = NULL;
    
    return nodo;
}


void
destruir_nodo(Nodo nodo){   
    /**
    * @param nodo Nodo a destruir
    *
    * @retval void 
    * 
    * Destructor del tipo Nodo
    */
    
    u32 i = 0;

    for (i=0;i<nodo->gradofwd;i++){
        nodo->nodosfw[i] = NULL;
    }
    
    free(nodo->capacidades);
    free(nodo->nodosfw);

    free(nodo);
    
    return;
}


void
agregar_nodo_fwd(Nodo nodo, Nodo fwd, u32 capacidad){
    /**
    * @param nodo Nodo al cual agregamos un nodo forward
    * @param fwd Nodo que agregamos
    * @param capacidad Capacidad del lado
    *
    * @retval void 
    * 
    * Funcion que relaciona un nodo con otro en modo forward, guardando
    * la capacidad del lado.
    * Se anula la ejecucion si se encuentra un error.
    * En caso de exito, no se devuelve nada.
    */
    
    if (nodo->capacidades == NULL){
        /*
         * Primer nodo a agregar, asignamos memoria.
         * nodo->capacidades y nodo->nodosfw estan intimamente relacionados
         * si uno no existe, el otro tampoco deberia, asi que con chequear
         * en uno de ellos, deberia bastar para saber el estado de ambos.
         */
        nodo->capacidades = (u32*)calloc(1,sizeof(u32));
        if (nodo->capacidades == NULL){
            perror("calloc");
            assert(nodo->capacidades!=NULL);
        }
        nodo->nodosfw = (Nodo*)calloc(1,sizeof(struct sNodo));
        if (nodo->nodosfw == NULL){
            perror("calloc");
            assert(nodo->nodosfw!=NULL);
        }
    }
    else{
        /*
         * No es el primer nodo, asi que reallocamos
         */

        nodo->capacidades = (u32*)realloc(\
                                nodo->capacidades,\
                                sizeof(u32)*(nodo->gradofwd + 2));
        if (nodo->capacidades == NULL){
            perror("realloc");
            assert(nodo->capacidades!=NULL);
        }
        nodo->nodosfw = (Nodo*)realloc(\
                                nodo->nodosfw,\
                                sizeof(Nodo)*(nodo->gradofwd + 2));
        if (nodo->nodosfw == NULL){
            perror("realloc");
            assert(nodo->nodosfw!=NULL);
        }
    }
    /*
     * En este momento, deberiamos tener el espacio de memoria apropiado
     * en la estructura, para meter el nodo y su capacidad
     */
    nodo->nodosfw[nodo->gradofwd] = fwd;
    nodo->capacidades[nodo->gradofwd] = capacidad;
    /*
     * Incrementamos la variable de cantidad de nodos
     */
    nodo->gradofwd++;

    return;
}

/** @} */ /*Final seccion "Nodo"*/


/** @defgroup path Funciones de la estructura Path
 *  @{
 */
/*Inicio seccion "Path"*/

Path
crear_path(Network network){
    /**
    * @param label Network que usamos para calcular el camino
    *
    * @retval path La estructura con el camino calculado
    * 
    * Esta funcion recorre el network y crea un camino hasta el "sink" (1)
    * Anula la ejecucion si encuentra un error.
    * En caso de exito, devuelve la estructura Path con el camino cargado.
    */

    Path path = NULL;
    Nodo nodo = NULL;
    Nodo nodofw = NULL;
    int found = 0;
    int should_end = 0;
    int source = 0;
    u32 ladosfw = 0;
    u32 i = 0;
    

    path = (Path)calloc(1,sizeof(struct sPath));
    if (path == NULL){
        perror("calloc");
        assert(path!=NULL);
    }

    path->nodos = NULL;
    path->padre = NULL;
    path->capacidad = NULL;
    path->bfs = NULL;
    path->largo_bfs = 0;
    path->size = 0;
    path->position = 0;
    path->flujo = 0;

    /*
     * En este punto ya tengo mi estructura, empiezo a recorrer el network
     * buscando el nodo "source" (0)
     */
    while (!found && (i < network-> cant_nodos)){
        /*
         * Mientras no encuentre el nodo "source" sigo iterando.
         * Nunca deberia salir del bucle por cumplirse la condicion
         * i > network -> cant_nodos ya que en ese caso quiere decir
         * que el network fue cargado erroneamente y no posee
         * nodo "source"
         */
        if (network->nodos[i]->label == 0){
            /*
             * Encontre el nodo "source"
             */
            found = 1;
            source = i;
        }
        else{
            i++;
        }
    }
    assert(i < network->cant_nodos);

    if (found){
        /*
         * Si encontre el nodo "source" empiezo a cargar el camino a partir
         * de ahi
         */

        nodo = network->nodos[source];
        agregar_nodo_path(path, nodo, 0);
        
        while (!should_end && nodo != NULL){
            i = 0;
            ladosfw = nodo->gradofwd;

            while (!should_end && i<ladosfw){
                /*
                * Voy a iterar mientras no me encuentre con el nodo "sink" (1)
                */
                nodofw = nodo->nodosfw[i];
                if (!nodo_en_path(path, nodofw)){
                    agregar_nodo_path(path, nodofw, nodo->capacidades[i]);
                }
                if (nodofw->label == 1){
                    /*
                     * Llegue al sink
                     */
                    should_end = 1;
                }
                i++;
            }

            nodo = path_siguiente(path);
        }

        if (should_end){
            /*
            * Una vez que termine de cargar todos los nodos y llegue al "sink"
            * asigno el valor final de la capacidad para saber el flujo maximo
            */
            path->flujo = path->capacidad[path->size-1];

            /*
            * Por ultimo, hago un recorrido de atras hacia adelante para
            * armar el camino
            */
            crear_bfs(path);
        }
    }
    
    return path;
}


void
destruir_path(Path path){
    /**
    * @param path Path a destruir
    *
    * @retval void 
    * 
     * Destructor del tipo Path
     */

    u32 i = 0;

    for (i=0;i<path->size;i++){
        path->nodos[i] = NULL;
        path->padre[i] = 0;
        path->capacidad[i] = 0;
    }
    for (i=0;i<path->largo_bfs;i++){
        path->bfs[i] = 0;
    }
    free(path->nodos);
    free(path->padre);
    free(path->capacidad);
    if (path->bfs != NULL){
        free(path->bfs);
    }
    free(path);
    
    return;
}


void
agregar_nodo_path(Path path, Nodo nodo, u32 capacidad){
    /**
    * @param path Path al cual agregar el nodo
    * @param nodo Nodo a agregar
    * @param capacidad Capacidad del lado
    *
    * @retval void 
    * 
     * Funcion que agrega el nodo al path
     */

    if (path -> size == 0){
        /*
         * Estoy agregando el "source", asi que tengo que asignar memoria
         */
        
        path->nodos = (Nodo*)calloc(1,sizeof(struct sNodo));
        if (path->nodos == NULL){
            perror("calloc");
            assert(path->nodos!=NULL);
        }
        path->padre = (u32*)calloc(1,sizeof(u32));
        if (path->padre == NULL){
            perror("calloc");
            assert(path->padre!=NULL);
        }
        path->capacidad = (u32*)calloc(1,sizeof(u32));
        if (path->capacidad == NULL){
            perror("calloc");
            assert(path->capacidad!=NULL);
        }

        /*
         * Ya tengo la memoria asignada, cargo el contenido
         */
        path->nodos[path->size] = nodo;
        path->padre[path->size] = 0;
        path->capacidad[path->size] = 0;
        path->size++;
    }
    else{
        /*
         * Si estoy aca, significa que estoy agregando un nodo que no es
         * el source, por lo tanto tengo que reallocar la memoria
         */
        path->nodos = (Nodo*)realloc(\
                        path->nodos,\
                        sizeof(Nodo)*(path->size + 2));
        if (path->nodos == NULL){
            perror("realloc");
            assert(path->nodos!=NULL);
        }
        path->padre = (u32*)realloc(\
                        path->padre,\
                        sizeof(u32)*(path->size + 2));
        if (path->padre == NULL){
            perror("realloc");
            assert(path->padre!=NULL);
        }
        path->capacidad = (u32*)realloc(\
                        path->capacidad,\
                        sizeof(u32)*(path->size + 2));
        if (path->capacidad == NULL){
            perror("realloc");
            assert(path->capacidad!=NULL);
        }

        /*
         * Memoria lista, asigno
         */
        path->nodos[path->size] = nodo;
        path->padre[path->size] = path->position;
        if (path->nodos[path->position]->label != 0){
            /*
             * Si estoy aqui, significa que este nodo esta siendo agregado
             * por otro que no es el source, luego necesito que la capacidad
             * sea el minimo valor entre lo que ya tenia, y la de este lado
             */
            if (path->capacidad[path->position] < capacidad){
                capacidad = path->capacidad[path->position];
            }
        }
        path->capacidad[path->size] = capacidad;
        path->size++;
    }

}


Nodo
path_siguiente(Path path){
    /**
    * @param path Path del cual pido el nodo actual
    *
    * @retval nodo Nodo siguiente, NULL en caso de no haber un siguiente.
    * 
    * Funcion que utilizo para avanzar el "puntero" al nodo actual y
    * al mismo tiempo, devolverlo.
    * Se devuelve NULL en caso de no encontrarse
    */
    Nodo nodo = NULL;
    
    if (path->position < path->size -1){
        /*
         * He llegado al final de la lista
         */

        path->position++;
        nodo = path->nodos[path->position];
    }    
    
    return nodo;
}


int
nodo_en_path(Path path, Nodo nodo){
    /**
    * @param path Path en donde busco el nodo
    * @param nodo Nodo que busco
    *
    * @retval int 
    * 
    * Funcion que devuelve 1 si el nodo ya fue agregado al path
    * y 0 si no.
    */
    int found = 0;
    u32 i = 0;
    
    while (!found && i<path->size){
        if (path->nodos[i]->label == nodo->label){
            found = 1;
        }
        i++;
    }

    return found;
}


void
crear_bfs(Path path){
    /**
    * @param path Path usado para crear el BFS
    *
    * @retval void 
    * 
    * Esta funcion recorre todo la estructura del path, para generar
    * hacia atras, el camino bfs
    */

    int should_end = 0;
    u32 i = 0;
    int j = 0;

    /*
     * Primero recorro mi estructura, para saber la longitud que tendra
     * el camino
     */

    i = path->size-1;
    while (!should_end){
        path->largo_bfs++;
        if (path->nodos[i]->label == 0){
            /*
             * Ya llegue al "source", asi que debo terminar
             */
            should_end = 1;
        }
        i = path->padre[i];
    }
    
    /*
     * Ahora asigno memoria al bfs
     */
    path->bfs = (u32*)calloc(path->largo_bfs,sizeof(u32));
    if (path->bfs == NULL){
        perror("calloc");
        assert(path->bfs!=NULL);
    }
    
    should_end = 0;
    
    i = path->size-1;
    j = path->largo_bfs -1;
    while (!should_end){
        path->bfs[j] = path->nodos[i]->label;
        if (path->nodos[i]->label == 0){
            /*
             * Ya llegue al "source", asi que debo terminar
             */
            should_end = 1;
        }
        i = path->padre[i];
        j--;
    }

    return;
}

/** @} */ /*Final seccion "Path"*/

void
imprimir_camino_y_flujo(Path path){
    /**
    * @param path Path usado para imprimir
    *
    * @retval void 
    * 
    * Funcion que imprime en la consola el camino y flujo (en caso de hallar
    * uno) o un mensaje informando que no hay camino
    */
    
    u32 i = 0;

    if (path->largo_bfs == 0){
        printf ("No existe camino :'(\n");
    }
    else{
        printf ("Existe el camino : ");
        while (i<path->largo_bfs){
            printf ("%u ", path->bfs[i]);
            i++;
        }
        printf ("\nCon flujo : %u\n", path->flujo);
    }
}
    